public class Main {


    /**
     *二叉树剪枝
     * @param root
     * @return
     */
    /*public TreeNode pruneTree(TreeNode root) {
        return dfs(root);
    }
    public TreeNode dfs(TreeNode root) {
        if(root == null) return null;
        //1. 递归左边
        TreeNode left = dfs(root.left);
        root.left = left;
        //2. 返回右边
        TreeNode right = dfs(root.right);
        root.right = right;
        //3. 返回值
        return root.val == 0 && root.left == null && root.right == null ? null : root;
    }*/

    //使用全局变量的优势
    /**
     * =验证二叉搜索树
     */
    /*long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean left = isValidBST(root.left);
        //剪枝
        if (left == false) return left;
        boolean cur = false;
        if (prev < root.val) cur = true;
        //剪枝
        if (cur == false) return cur;
        prev = root.val;
        boolean right = isValidBST(root.right);
        return left && right && cur;

    }*/


    /**
     * 二叉搜索树中第K小的元素
     * @param root
     * @param k
     * @return
     */    /*
    int count;
    int ret;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return ret;

    }
    public void dfs(TreeNode root) {
        //中序遍历
        if(root == null) return;
        dfs(root.left);
        if(count == 0) return;
        count--;
        ret = root.val;
        if(count == 0) return;
        dfs(root.right);
    }*/


    /**
     * 二叉树的所有路径
     */
    /*List<String> ret = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        String path = "";
        dfs(root, path);
        return ret;
    }

    public void dfs(TreeNode root, String path) {
        if (root == null) {
            return;
        }
        if(root.left == null && root.right == null) {
            ret.add(path+root.val+"");
        }
        path = path + root.val + "->";
        dfs(root.left, path);
        dfs
*/
}
